(파이썬 S/W 문제해결 기본) List2 - 4836번 4837번 4839번 4843번

4836번 - 색칠하기

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

T = int(input())

for test_case in range(1, T + 1):
red_color = []
blue_color = []

    N = int(input())
    for i in range(N):
        purple_color = 0
        r1, c1, r2, c2, color = map(int, input().split())

        for y in range(c1, c2+1):
            for x in range(r1, r2+1):
                if color==1:
                    red_color.append([x,y])
                elif color==2:
                    blue_color.append([x,y])


        for red in red_color:
            for blue in blue_color:
                if red == blue:
                    purple_color += 1

    print("#{} {}".format(test_case, purple_color))

---

4837번 - 부분집합의 합

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

부분집합을 구할 때, 비트연산을 사용

set_A = [num for num in range(1,13)]
subset_A = [[set_A[j] for j in range(12) if i&(1<<j)] for i in range(1<<12)]

T = int(input())

for test_case in range(1, T + 1):
N, K = map(int, input().split()) # N : 부분집합 원소의 수, K : 부분집합의 합
cnt=0

    for subset in subset_A:
        if len(subset)==N and sum(subset)==K:
            cnt+=1

    print("#{} {}".format(test_case, cnt))

---

4839번 - 이진탐색

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

이진탐색 재귀함수

def binary_search(left, right, key, cnt):
if left>right:
return None
else:
middle = (left+right)//2
if key==middle:
return cnt
elif key<middle:
return binary_search(left, middle, key, cnt+1)
else:
return binary_search(middle, right, key, cnt+1)

T = int(input())

for test_case in range(1, T + 1):
P, A, B = map(int, input().split())

    winner = 0
    if binary_search(1, P, A, 0)<binary_search(1, P, B, 0):
        winner ='A'
    elif binary_search(1, P, A, 0)>binary_search(1, P, B, 0):
        winner = 'B'

    print("#{} {}".format(test_case, winner))

---

4843번 - 특별한 정렬

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

정렬시키고 양끝에서 안쪽으로 iter 반복

def special_sort(arr):
s_arr = sorted(arr)
length = len(s_arr)

    special_arr = []
    for i in range(length):
        if i%2==0:
            special_arr.append(s_arr[length-1-i//2])
        else:
            special_arr.append((s_arr[i//2]))
    return special_arr

T = int(input())

for test_case in range(1, T + 1):
N = int(input())
arr_N = [int(num) for num in input().split()]

    print('#{} '.format(test_case), end='')
    for a in special_sort(arr_N)[:10]:
        print(a, end=' ')
    print()

---